Computer security is a major concern for networked computers. A firewall is commonly used to permit, deny, or proxy data connections between computers. Generally, most firewalls operate by blocking all unsolicited inbound data connections and only allowing solicited inbound connections. Solicited inbound connections are inbound connections sent in reply to an originating outbound request. Identifying whether a connection is solicited or not is determined by matching inbound connections against an internal state table. Entries are added to the internal state table whenever an outbound request is sent.
Typical firewall implementations perform lookups against this internal state table with or without hashing. Under normal circumstances hashing is desirable because it provides highly efficient lookups of entries in the internal state table. But, if an attacker determines the hashing algorithm used by the firewall, the attacker can craft packets that will create duplicate hash table entries. This leads to exceedingly long chains for an entry in the internal state table and thus, an extreme degradation of performance. Because the hashing algorithm only utilizes the data required to match the inbound connection based on the simple 5-tuple configuration (e.g., local port, local address, destination port, destination address, and protocol), 5-tuples can be easily guessed and manipulated to create collisions in the internal state table. Thus, firewalls that implement hashing are susceptible to denial of service attacks through extreme degradation of performance.